package exercises.newcoder.solution;

import java.util.ArrayList;

/**
 * <a href="https://www.nowcoder.com/practice/f983806a2ecb4106a17a365a642a9632?tpId=202&&tqId=38722&rp=1&ru=/activity/oj&qru=/ta/code-written-high/question-ranking">
 * WC13 分割回文串</a>
 *
 * @author or2
 * @Description 给定一个字符串s，分割s使得s的每一个子串都是回文串
 * 返回所有的回文分割结果。（注意：返回结果的顺序需要和输入字符串中的字母顺序一致。）
 * @create 2021年09月18日 时间: 17:52
 */
public class Partition {
    /**
     * @param s string字符串
     * @return string字符串ArrayList<ArrayList <>>
     */
    public ArrayList<ArrayList<String>> partition(String s) {
        int totalLength = s.length();
        /*存储答案*/
        ArrayList<ArrayList<String>> ans = new ArrayList<>();
//        预先验证临界条件, 动态规划不担心越界
        /*若只有一个, 直接判断返回*/
        if (totalLength == 1) {
            ArrayList<String> layer = new ArrayList<>();
            layer.add(s);
            ans.add(layer);
            /*jdk11 - ans.add(new ArrayList<>(List.of(s)));*/
            return ans;
        }
        /*若只有二个, 直接判断返回*/
        if (totalLength == 2) {
            ArrayList<String> ans1 = new ArrayList<>();
            if (s.charAt(0) == s.charAt(1)) {
                /*jdk11 - ans.add(new ArrayList<>(List.of(s)))*/
                ans1.add(s);
                ans.add(ans1);
            }
            /*jdk11 - ans.add(new ArrayList<>(List.of(s.substring(0, 1), s.substring(1, 2))));*/
            ans1 = new ArrayList<>();
            ans1.add(s.substring(0, 1));
            ans1.add(s.substring(1, 2));
            ans.add(ans1);
            return ans;
        }
        /*动态规划*/
        int[][] dp = new int[totalLength][totalLength];

        for (int i = 0; i < totalLength; i++) {
            dp[i][i] = 1;
        }
        for (int i = 0; i < totalLength - 1; i++) {
            if (s.charAt(i + 1) == s.charAt(i)) {
                dp[i][i + 1] = 1;
            }
        }

//        生产动态规划矩阵
        for (int i = 2; i < totalLength; i++) {
            for (int j = 0; j < totalLength - i; j++) {
                if (dp[j + 1][j + i - 1] == 1) {
                    if (s.charAt(j) == s.charAt(j + i)) {
                        dp[j][j + i] = 1;
                        continue;
                    }
                }
                dp[j][j + i] = 0;
            }
        }

//        根据动态规划矩阵深度有限遍历
        int startIndex = 0;
        ArrayList<String> layer = new ArrayList<>();
        dfs(startIndex, dp, ans, layer, s);

        return ans;
    }

    private void dfs(int startIndex, int[][] dp, ArrayList<ArrayList<String>> ans, ArrayList<String> layer, String s) {
        //        递归终止条件
        if (startIndex == dp.length) {
            layer = new ArrayList<>(layer);
            ans.add(layer);
            return;
        }

        for (int i = startIndex; i < dp.length; i++) {
            if (dp[startIndex][i] == 1) {
                layer.add(s.substring(startIndex, i + 1));
                dfs(i + 1, dp, ans, layer, s);
//                回溯
                layer.remove(layer.size() - 1);
            }
        }
    }
}
